#include "bits/stdc++.h"
using namespace std;


/**
 * @brief 给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。

如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为 优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。

返回 优质数对 的总数。
 * 
 */
class Solution {
    #define ll long long
public:
    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        ll res = 0;

        unordered_map<int, int> count1;
        unordered_map<int, int> count2;

        int max_value = 0;

        for (int item : nums1) {
            ++count1[item];
            max_value = max(max_value, item);
        }

        for (int item : nums2) {
            ++count2[item];
        }

        for (const auto pair : count2) {
            int a = pair.first;
            int cnt = pair.second;

            for (int i = a * k; i <= max_value; i += a * k) {
                if (count1.count(i)) {
                    res += 1L * cnt * count1[i];
                }
            }
        }

        return res;
    }
};